package org.example.Soution003;

public class DynamicProgrammingThief {
    public static void main(String[] args) {
        DynamicProgrammingThief dpt = new DynamicProgrammingThief();
        int[] nums=new int[]{2,7,9,3,1};
        System.out.println(dpt.rob(nums));
    }

    public int rob(int[] nums) {
        //当前能偷的最大金额为Max（偷邻居，偷当前）
        int n= nums.length;;
        int[] maxMoney=new int[n];
        maxMoney[0]=nums[0];
        if(n==1){
            return maxMoney[0];
        }
        maxMoney[1]=Math.max(maxMoney[0],nums[1]);
        for(int i=2;i<n;i++) {
            maxMoney[i] = Math.max(maxMoney[i - 2] + nums[i], maxMoney[i - 1]);
        }
        return maxMoney[n-1];
    }
}
